#include <bits/stdc++.h>
#include <algorithm>
#define INF 1 << 30
using namespace std;
constexpr int MAXV = 100, MAXE = 100;
struct edge {int to, cost;};
typedef pair<int, int> P; // first是最短距离, second是顶点的编号
int V; 
vector<edge> G[MAXV]; // 所有节点的边
int d[MAXV]; // 节点的最短距离

void dijsktra(int s) {
    priority_queue<edge, vector<P>, greater<P>> q;
    fill(d, d + V, INF); d[s] = 0;
    q.push(P(0, s));
    while (!q.empty()) {
        P p = q.top(); q.pop();
        int v = p.second;
        if (d[v] < p.first) continue; // 这一步相当于说删去重复添加但是没有更新的节点
        for (int i = 0; i < G[v].size(); i++) {
            edge e = G[v][i];
            if (d[e.to] > d[v] + e.cost) {
                d[e.to] = d[v] + e.cost;
                q.push(P(d[e.to], e.to)); // 可能会存在重复添加的情况, 但是在之前的一步中都删除了这种情况
            }
        }
    }
}